#include<iostream>
using namespace std;
void swap(int*a,int*b)
{

int tmp=*a;
*a=*b;
*b=tmp;




}


void adjustup(int*a,int child)//建小堆
{
  int parent=(child-1)/2;
  while(child>0)
  {  if(a[parent]>a[child])
   {
     swap(&a[parent],&a[child]);
    // parent=child;
     //child=child*2+1;
        child=parent;
        parent=(child-1)/2;


   }
   else
   {
     break;

   }
    
  }
}
void adjustdown(int*a,int parent,int n)
{
  int child=parent*2+1;
  while(child<n)
  {
    if(child+1<n&&a[child+1]<a[child])
     {

     child++;

     }
     if(a[child]<a[parent])
     {
        swap(&a[child],&a[parent]);
        //child=parent;
        //parent=(child-1)/2;
           parent=child;
          child=parent*2+1;

     }
     else
     {
        break;


     }
   

  }




}
void heapsort(int*a,int n)
{
 //for(int i=1;i<n;i++)
 //{adjustup(a,i,n);}
   
 for(int i=(n-1-1)/2;i>=0;i--)
 {adjustdown(a,i,n);}

   int end=n-1;
   while(end>0)
   {
     swap(&a[0],&a[end]);
     adjustdown(a,0,end);
     end--;



   }



}


int main()
{

  int arr[10]={5,9,8,56,78,15,23,95,46,55};
  heapsort(arr,10);
  for(int i=0;i<10;i++)
  {cout<<arr[i]<<" ";}




}